package com.bo.day20240912;

import java.util.LinkedList;
import java.util.Queue;

/**
 * 二叉树的先序序列化和反序化
 * <p>
 * 图解： https://cloud.fynote.com/share/d/1HKzVHbl
 *
 * @Author: gpb
 * @Date: 2024/9/12 16:13
 * @Description:
 */
public class SerializeAndReconstructTree {

    public static void main (String[] args) {
        int maxLevel = 5;
        int maxValue = 100;
        int testTimes = 1000000;
        System.out.println("test begin");
        for (int i = 0; i < testTimes; i++) {
            Node head = generateRandomBST(maxLevel, maxValue);
            Queue<String> pre = preSerial(head);
            System.out.println("先序序列化：" + pre);
            Queue<String> level = levelSerial(head);
            System.out.println("按层序列化：" + level);
            Node preBuild = buildTreeByPre(pre);
            Node levelBuild = buildTreeByLevel(level);
            if (!isSameValueStructure(preBuild, levelBuild)) {
                System.out.println("Oops!");
            }
        }
        System.out.println("test finish!");

    }

    public static class Node {
        public int value;
        public Node left;
        public Node right;

        public Node (int data) {
            this.value = data;
        }
    }

    /**
     * 先序序列化二叉树
     *
     * @param head
     * @return
     */
    public static Queue<String> preSerial (Node head) {
        Queue<String> queue = new LinkedList<>();
        doPreSerial(head, queue);
        return queue;
    }

    /**
     * 先序序列化二叉树核心逻辑
     *
     * @param head
     * @param queue
     */
    private static void doPreSerial (Node head, Queue<String> queue) {
        // 如果节点为空，则添加null占位
        if (head == null) {
            queue.add(null);
        } else {
            queue.add(String.valueOf(head.value));
            // 递归左子树
            doPreSerial(head.left, queue);
            // 递归右字数
            doPreSerial(head.right, queue);
        }
    }

    /**
     * 根据先序反序化成二叉树
     *
     * @param queue
     * @return
     */
    public static Node buildTreeByPre (Queue<String> queue) {
        if (queue == null || queue.size() == 0) {
            return null;
        }
        return doBuildTreeByPre(queue);
    }

    /**
     * 根据先序反序化成二叉树核心逻辑
     *
     * @param queue
     * @return
     */
    private static Node doBuildTreeByPre (Queue<String> queue) {
        String poll = queue.poll();
        if (poll == null) {
            return null;
        }
        Node node = new Node(Integer.parseInt(poll));
        // 先恢复左树
        node.left = doBuildTreeByPre(queue);
        // 在恢复右树
        node.right = doBuildTreeByPre(queue);
        return node;
    }

    /**
     * 安层序列化二叉树
     *
     * @param head
     * @return
     */
    public static Queue<String> levelSerial (Node head) {
        Queue<String> ans = new LinkedList<>();
        if (head == null) {
            return ans;
        }
        Queue<Node> queue = new LinkedList<>();
        queue.add(head);
        ans.add(String.valueOf(head.value));
        while (!queue.isEmpty()) {
            Node poll = queue.poll();
            if (poll.left != null) {
                queue.offer(poll.left);
                ans.add(String.valueOf(poll.left.value));
            } else {
                ans.add(null);
            }
            if (poll.right != null) {
                queue.offer(poll.right);
                ans.add(String.valueOf(poll.right.value));
            } else {
                ans.add(null);
            }
        }
        return ans;
    }

    /**
     * 按层反序列化二叉树
     *
     * @param queue
     * @return
     */
    public static Node buildTreeByLevel (Queue<String> queue) {
        if (queue == null || queue.size() == 0) {
            return null;
        }
        Node head = generateNode(queue.poll());
        if (head == null) {
            return head;
        }
        Queue<Node> ans = new LinkedList<>();
        ans.add(head);
        while (!ans.isEmpty()) {
            // 弹出头节点
            Node poll = ans.poll();
            // 分别弹出头节点左右节点
            poll.left = generateNode(queue.poll());
            poll.right = generateNode(queue.poll());
            // 如果左子树不为空,说明还有子树,则把左节点入队
            if (poll.left != null) {
                ans.add(poll.left);
            }
            // 如果右子树不为空,说明还有子树,则把右节点入队
            if (poll.right != null) {
                ans.add(poll.right);
            }
        }
        return head;
    }


    public static Node generateNode (String val) {
        if (val == null) {
            return null;
        }
        return new Node(Integer.valueOf(val));
    }

    // for test
    public static Node generateRandomBST (int maxLevel, int maxValue) {
        return generate(1, maxLevel, maxValue);
    }

    // for test
    public static Node generate (int level, int maxLevel, int maxValue) {
        if (level > maxLevel || Math.random() < 0.5) {
            return null;
        }
        Node head = new Node((int) (Math.random() * maxValue));
        head.left = generate(level + 1, maxLevel, maxValue);
        head.right = generate(level + 1, maxLevel, maxValue);
        return head;
    }

    // for test
    public static boolean isSameValueStructure (Node head1, Node head2) {
        if (head1 == null && head2 != null) {
            return false;
        }
        if (head1 != null && head2 == null) {
            return false;
        }
        if (head1 == null && head2 == null) {
            return true;
        }
        if (head1.value != head2.value) {
            return false;
        }
        return isSameValueStructure(head1.left, head2.left) && isSameValueStructure(head1.right, head2.right);
    }

    // for test
    public static void printTree (Node head) {
        System.out.println("Binary Tree:");
        printInOrder(head, 0, "H", 17);
        System.out.println();
    }

    public static void printInOrder (Node head, int height, String to, int len) {
        if (head == null) {
            return;
        }
        printInOrder(head.right, height + 1, "v", len);
        String val = to + head.value + to;
        int lenM = val.length();
        int lenL = (len - lenM) / 2;
        int lenR = len - lenM - lenL;
        val = getSpace(lenL) + val + getSpace(lenR);
        System.out.println(getSpace(height * len) + val);
        printInOrder(head.left, height + 1, "^", len);
    }

    public static String getSpace (int num) {
        String space = " ";
        StringBuffer buf = new StringBuffer("");
        for (int i = 0; i < num; i++) {
            buf.append(space);
        }
        return buf.toString();
    }

}
